home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 February: Tool Chest / Apple Developer CD Series Tool Chest February 1996 (Apple Computer)(1996).iso / Sample Code / AOCE Sample Code / PowerTalk Access Modules / Sample SMSAM / SampleSMSAM Source / BuildingBlocks / Queues.cp < prev    next >
Encoding:
Text File  |  1995-07-28  |  7.9 KB  |  406 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        Queues.cp
  3.  
  4.     Copyright:    © 1991-1994 by Apple Computer, Inc.
  5.                 All rights reserved.
  6.  
  7.     Part of the AOCE Sample SMSAM Package.  Consult the license
  8.     which came with this software for your specific legal rights.
  9.  
  10. */
  11.  
  12.  
  13.  
  14. #ifndef __QUEUES__
  15. #include "Queues.h"
  16. #endif
  17.  
  18. #ifndef __MEMORY__
  19. #include <Memory.h>
  20. #endif
  21.  
  22. #ifndef    __DEBUGASSERT__
  23. #include "DebugAssert.h"
  24. #endif
  25.  
  26. #ifndef    __DEBUGGINGGEAR__
  27. #include "DebuggingGear.h"
  28. #endif
  29.  
  30. /***********************************|****************************************/
  31.  
  32. #pragma segment Queue
  33.  
  34. /***********************************|****************************************/
  35.  
  36. void* const kBadObject = (void*) 0xFFFFFFFF;
  37.  
  38. extern void BreakStr ( const Str255 str );
  39.  
  40. /***********************************|****************************************/
  41.  
  42. class TQueueItem  {
  43.     public:                            TQueueItem ( void * object, 
  44.                                                 TQueueItem * prev = nil,
  45.                                                 TQueueItem * next = nil );
  46.                                     ~TQueueItem ( );
  47.                                     
  48.         void *                        GetObject ( ) const { return fItem; }
  49.         
  50.         TQueueItem *                GetNextItem () const { return fNextItem; }
  51.         TQueueItem *                GetPrevItem () const { return fPrevItem; }
  52.         
  53.         void                        SetNextItem ( TQueueItem * next ) { fNextItem = next; }
  54.         void                        SetPrevItem ( TQueueItem * prev ) { fPrevItem = prev; }
  55.  
  56.     protected:
  57.         TQueueItem *                fNextItem;
  58.         TQueueItem *                fPrevItem;
  59.         void *                        fItem;
  60. };
  61.  
  62. /***********************************|****************************************/
  63.  
  64. TQueueItem::TQueueItem ( void * o, TQueueItem * prev, TQueueItem * next ) :
  65.     fItem ( o ),
  66.     fNextItem ( next ),
  67.     fPrevItem ( prev )
  68. {
  69.     if ( next )
  70.         next->SetPrevItem ( this );
  71.     
  72.     if ( prev )
  73.         prev->SetNextItem ( this );
  74. }
  75.  
  76. /***********************************|****************************************/
  77.  
  78. TQueueItem::~TQueueItem ( )
  79. {
  80.     if ( fPrevItem )
  81.         fPrevItem->SetNextItem ( fNextItem );
  82.     
  83.     if ( fNextItem )
  84.         fNextItem->SetPrevItem ( fPrevItem );
  85. }
  86.  
  87. /***********************************|****************************************/
  88. /***********************************|****************************************/
  89. /***********************************|****************************************/
  90.  
  91. TQueue::TQueue ( Boolean ownsObjects ):
  92.     fFirst ( nil ),
  93.     fLast ( nil ),
  94.     fSpareQueueItems ( nil ),
  95.     fCount ( 0 ),
  96.     fOwnsObjects ( ownsObjects )
  97. {
  98. }
  99.  
  100. /***********************************|****************************************/
  101.  
  102. TQueue::~TQueue ()
  103. {
  104.     if ( fCount > 0 && fOwnsObjects )
  105.         DeleteAll ();
  106. }
  107.  
  108. /***********************************|****************************************/
  109.  
  110. void
  111. TQueue::SetOwnsObjects ( Boolean ownsObjects )
  112. {
  113.     fOwnsObjects = ownsObjects;
  114. }
  115.  
  116. /***********************************|****************************************/
  117.  
  118. Boolean
  119. TQueue::GetOwnsObjects () const
  120. {
  121.     return fOwnsObjects;
  122. }
  123.  
  124. /***********************************|****************************************/
  125.  
  126. unsigned long
  127. TQueue::Find ( const void* object ) const
  128. {
  129.     TQueueItem * queueItem = fFirst;
  130.     unsigned long index = 1;
  131.     
  132.     while ( queueItem )
  133.         if ( object == queueItem->GetObject() )
  134.             return index;
  135.         else
  136.         {    
  137.             index ++;
  138.             queueItem = queueItem->GetNextItem();
  139.         }
  140.         
  141.     return 0;
  142. }
  143.  
  144. /***********************************|****************************************/
  145.  
  146.  
  147. TQueueItem*
  148. TQueue::GetQueueItem ( unsigned long index ) const
  149. {
  150.     TQueueItem * item = fFirst;
  151.     
  152.     if ( index <= fCount )
  153.     {
  154.         while ( item && ( index > 1 ) )
  155.         {
  156.             item = item->GetNextItem();
  157.             index -- ;
  158.         }
  159.         
  160.         return item;
  161.     }
  162.     else
  163.         return nil;
  164. }
  165.  
  166. /***********************************|****************************************/
  167.  
  168. void*
  169. TQueue::Get ( unsigned long index ) const
  170. {
  171.     TQueueItem * item = GetQueueItem ( index );
  172.     
  173.     if ( item )
  174.         return item->GetObject();
  175.     
  176. #if debug
  177.         BreakStr ( "\pinvalid index" );
  178. #endif
  179.     return nil;
  180.     
  181. }
  182.  
  183. /***********************************|****************************************/
  184.  
  185. void*
  186. TQueue::operator [] ( unsigned long index ) const
  187. {
  188.     TQueueItem * item = GetQueueItem ( index - 1 );
  189.     
  190.     if ( item )
  191.         return item->GetObject();
  192.     
  193. #if debug
  194.         BreakStr ( "\pinvalid index" );
  195. #endif
  196.     return nil;
  197. }
  198.  
  199. /***********************************|****************************************/
  200.  
  201. void TQueue::Append ( void * object )
  202. {
  203.     //    Insert as the last item in the queue.
  204.     TQueueItem * newItem = new TQueueItem ( object, fLast, nil );
  205.     fLast = newItem;
  206.     if ( !fFirst )
  207.         fFirst = newItem;
  208.     fCount ++;
  209. }
  210.  
  211. /***********************************|****************************************/
  212.  
  213. void
  214. TQueue::Insert ( unsigned long index, void* object )
  215. {
  216. #if debug
  217.     if ( index == 0 )
  218.     {
  219.         BreakStr ( "\pzero user index" );
  220.         return;
  221.     }
  222. #endif
  223.     
  224.     //    Constrain 1 <= index <= fCount
  225.     index = ( index < 1 ) ? 1 : ( index >= fCount ) ? fCount : index;
  226.  
  227.     if ( index > 1 )
  228.     {
  229.         if ( index < fCount )
  230.         {
  231.             TQueueItem * itemToInsert = GetQueueItem ( index );
  232.             TQueueItem * newItem = new TQueueItem ( object, itemToInsert, itemToInsert->GetNextItem() );
  233.         }
  234.         else
  235.         {
  236.             //    Insert as the last item in the queue.
  237.             TQueueItem * newItem = new TQueueItem ( object, fLast, nil );
  238.             fLast = newItem;
  239.         }
  240.     }
  241.     else
  242.     {
  243.         {
  244.             //    Insert as the first item in the queue.
  245.             TQueueItem * newItem = new TQueueItem ( object, nil, fFirst );
  246.             fFirst = newItem;
  247.             
  248.             if ( !fLast )
  249.                 fLast = newItem;
  250.         }
  251.     }
  252.     
  253.     fCount++;
  254. }
  255.  
  256. /***********************************|****************************************/
  257.  
  258. void*
  259. TQueue::Remove ( unsigned long index )
  260. {
  261. #if debug
  262.     if ( !IsValidIndex ( index ) )
  263.     {
  264.         // BreakStr ( "\pTQueue::Remove(), bad index" );
  265.         return nil;
  266.     }
  267. #endif
  268.     TQueueItem * itemToRemove = GetQueueItem ( index );
  269.     
  270.     if ( itemToRemove )
  271.     {
  272.         if ( fFirst == itemToRemove )
  273.             fFirst = itemToRemove->GetNextItem();
  274.         
  275.         if ( fLast == itemToRemove )
  276.             fLast = itemToRemove->GetPrevItem();
  277.         
  278.         if ( itemToRemove->GetPrevItem() )
  279.             itemToRemove->GetPrevItem()->SetNextItem ( itemToRemove->GetNextItem() );
  280.         
  281.         if ( itemToRemove->GetNextItem() )
  282.             itemToRemove->GetNextItem()->SetPrevItem ( itemToRemove->GetPrevItem() );
  283.  
  284.         //    Stick this item into the queue of 'spare' queue items;
  285.         itemToRemove->SetNextItem ( fSpareQueueItems );
  286.         fSpareQueueItems = itemToRemove;    
  287.     
  288.         fCount --;
  289.         
  290.         return itemToRemove->GetObject();
  291.     }
  292.     
  293.     return nil;
  294. }
  295.  
  296. /***********************************|****************************************/
  297.  
  298. Boolean
  299. TQueue::Delete ( unsigned long index )
  300. {
  301.     void* object = Remove ( index );
  302.  
  303.     if ( object )
  304.     {
  305.         DeleteObject ( object );
  306.         return true;
  307.     }
  308.     else
  309.     {
  310.         return false;
  311.     }
  312. }
  313.  
  314. /***********************************|****************************************/
  315.  
  316. Boolean
  317. TQueue::Remove ( const void* object )
  318. {
  319.     unsigned long index = Find ( object );
  320.  
  321.     if ( index > 0 )
  322.     {
  323.         Remove ( index );
  324.         return true;
  325.     }
  326.     else
  327.     {
  328.         return false;
  329.     }
  330. }
  331.  
  332. /***********************************|****************************************/
  333.  
  334. void
  335. TQueue::RemoveAll ()
  336. {
  337.     //    Move all of the stuff from the queue into the fSpareQueueItems list.
  338.     
  339.     if ( fLast )
  340.     {
  341.         fLast->SetNextItem ( fSpareQueueItems );
  342.         fSpareQueueItems = fFirst;
  343.     }
  344.     
  345.     fFirst = fLast = nil;
  346.     fCount = 0;
  347. }
  348.  
  349. /***********************************|****************************************/
  350.  
  351. Boolean
  352. TQueue::Delete ( void* object )
  353. {
  354.     Boolean removed = Remove ( object );
  355.  
  356.     if ( removed )
  357.         DeleteObject ( object );
  358.  
  359.     return removed;
  360. }
  361.  
  362. /***********************************|****************************************/
  363.  
  364. void
  365. TQueue::DeleteAll ()
  366. {
  367.     TQueueItem * item = fFirst;
  368.     
  369.     while ( item )
  370.     {
  371.         DeleteObject ( item->GetObject() );
  372.         item = item->GetNextItem();
  373.     }
  374.     
  375.     fCount = 0;
  376. }
  377.  
  378. /***********************************|****************************************/
  379.  
  380. void
  381. TQueue::DeleteObject ( void* object ) const
  382. {
  383.     delete object;
  384. }
  385.  
  386. /***********************************|****************************************/
  387.  
  388. ostream&
  389. TQueue::operator >> ( ostream& s ) const
  390. {
  391.     // subclasses should stream their name, then call this method
  392.  
  393.     s << " @ " << (void*) this << ": (" << Count() << ") ";
  394.  
  395.     for ( unsigned long index = 0; index < fCount; index++ )
  396.     {
  397.         if ( index > 0 )
  398.             s << ",";
  399.  
  400.         s << Get ( index + 1 );
  401.     }
  402.  
  403.     return s;
  404. }
  405.  
  406. /***********************************|****************************************/